RSA(非对称加密)

前言

RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性

关于RSA

工作原理

算法参数
RSA的安全性依赖于大数分解。换句话说，RSA的难度与大数分解难度等价，一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译。这点将在下述对 N 的讨论着重体现。
ps：大整数又称为高精度整数，其含义就是用基本数据类型无法存储其精度的整数。

加密算法
从上图可以看出RSA加密过程可以用下面这个公式表示

c=m^{e}mod N

RSA的密文是对代表了明文的数字的E次方求mod N的结果。换句话说，就是将明文和自己做E次乘方，然后将其结果除以N求余数，这个余数就是密文。

加密公式中出现了两个数——E和N，到底都是什么数呢？RSA的加密是求明文的E次方mod N，因此只要知道E和N这两个数，任何人都可以完成加密的运算。所以说，E和N是RSA加密的密钥，也就是说，E和N的组合就是公钥。

不过，E和N并不是随便什么数都可以的，它们是经过严密计算得出的。其中E是加密（Encryption）的首字母，N是数字（Number）首字母。

有一个很容易引起误解的地方——E和N这两个数并不是密钥对（公钥和私钥的密钥对）。E和N两个数才组成一个公钥，因此我们一般会写出“公钥是（E，N）”或者“公钥是{E，N}”这样的形式，将E和N用括号括起来。

解密算法

m=c^{d}mod N

该公式表示对密文的数字的D次方求mod N就可以得到明文。换句话说，将密文自己做D次乘法，再对其结果除以N求余数，就可以得到明文。

这里使用的数字N和加密时使用的数字N是相同的。数D和数N组成起来就是RSA的解密密钥，因此D和N的组合就是私钥。只有知道D和N两个数的人才能够完成解密的运算。由于N是公钥的一部分，是公开的，因此单独将D称为私钥也是可以的。

在RSA中，加密和解密的形式是相同的。加密是求“E次方的modN”，而解密则是求“D次方的modN”。

当然，D也并不是随便什么数都可以的，作为解密密钥的D，和数字E有着相当紧密的联系。否则，用E加密的结果可以用D来解密这样的机制是无法实现的。

D是解密（Decryption）的首字母，N是数字（Number）的首字母。

生成密匙对
由上述分析可知，加解密的过程需要三个参数 E、D、N，那么这三个参数该怎么生成呢？由于 E 和 N 是公钥，D 和 N 是私钥，求这三个数的过程就是生成密钥对。生成步骤如下：
1、求N
首先准备两个很大的质数P、Q。上述所说的算法安全性与大数分解有关，就体现在这了，我们反过来想，如果P和Q选的很小，那对于N的求解将会变得非常简单，密码就容易被破译；但是物极必反，也不能选的太大，太大会使得计算时间大大延长。

P*Q=N

2、求φ
φ这个数在加密解密的过程中都不曾出现，它只出现在生成密钥对的过程中。由下列公式求得

φ=(P-1)*(Q-1)

3、求E
e 的求取基于上述的 φ 值。首先明确 e 的取值范围 1<e<φ，并且 gcd(φ,e)=1（φ 与 e 的最大公约数为1，即两者互质）。之所以要加上1这个条件，是为了保证一定存在解密时需要使用的参数 D

gcd(φ,e)=1

4、求D
d 的求取基于上述的 e 值和 φ 值。首先明确 d 的取值范围 1<d<φ，并且 gcd(φ,d)=1。d 的求解方式如下

e*d mod φ=1

例子

常见大整数N的分解方法
对于常规得CTF题来说，通常会给大家公钥指数 E 和公共模数 N，而这个模数 N 是非常大得数字。我们要做的是将它分解成两个指数 p，q，进而求得 φ，再根据公式求得私钥指数，最后将密文转换成明文。
如何将大整数 N 分解呢？
1、当 N 的长度较小时，采用爆破
2、当 N 满足因数p、q相差较小或相差很大时，可以采用离线工具yafu来分解
3、当 N 的位数过大时，且不满足上述条件，可以用在线网站 factordb。该网站类似于彩虹表，将已被分解的大数结果存储起来，只需要输入查询即可。

ps:yafu使用方式
1、使用cmd进入yafu的解压目录，输入yafu-x64进入命令行，最常用的命令是factor(n)，将n值分解。

factor(需要分解的大数)

2、使用yafu的时候遇到mismatched parens
//这是因为在命令行里不支持过长的位数。
新建一个文件p.txt，内容里写上n的值，最后面一定要换行。
然后运行命令为

yafu-x64 "factor(@)" -batchfile 1.txt

注意：运行后，1.txt就会消失了

逆元
逆元是什么？为什么突然讨论逆元？
还记得上面求解私钥指数d的公式吗？

e*d mod φ=1

这个公式也可以写成

e*d ≡ 1(mod φ)

如果一个线性同余方程 ax ≡ 1(mod b)，则 x 称为a mod b的逆元，记作a-1。一个数有逆元的充分必要条件是gcd(a,b)=1，此时逆元唯一存在 。
此处为什么讨论逆元呢？其一，RSA中有逆元的概念；其二，中国剩余定理(CRT)可与 RSA 算法结合来进行加解密。CRT又逃不开逆元的概念，所以就说了。逆元也是数论中一个十分重要的概念，当我们要求 (a/b)mod p的值，且a很大，大到会溢出；或者说b很大，达到会爆精度。无法直接求得a/b的值时，我们就要用到乘法逆元。
所以上述求解私钥指数d，可以说 e的逆元是 d mod φ

拓展

费马小定理
如果 p 是一个质数，而整数 a 不是 p 的倍数，则

a^p−1 ≡ 1 (mod p)

可得

a * a^p−2 ≡ 1 (mod p)
所以 a 的逆元即为 a p-2 (mod p)
之后利用快速幂求解

typedef long long ll;
ll mod = 1e9 + 7;
ll quick_pow(ll base,ll idx){
    ll ans = 1;
    while(idx){
        if(idx & 1){
            ans *= base;
            ans %= mod;
        }
        base *= base;
        base %= mod;
        idx >>= 1;
    }
    return ans;
}

ll inv(ll a){
    return quick_pow(a,mod-2);
}

欧几里得
逆元的含义决定了ax ≡ 1(mod b)等价于ax = kb+1
void exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}

中国剩余定理（CRT）加速RSA算法

CRT简介
网上介绍很多，具体可以参考：http://t.csdn.cn/mqOAV
降N
前面多次讨论过了，RSA的难点就在于对于大整数 N 的分解。有没有啥方法能简化这个过程呢？
有，就是上述的中国剩余定理。由中国剩余定理可知，设 p 和 q 是互相独立的大素数，n 为 p*q，对于任意 (m1, m2)，且 0<=m1< p，0<=m2< q
必然存在一个唯一的m ，0<=m< n，使得

m1 = m mod p
m2 = m mod q

换句话说，给定一个(m1,m2)，其满足上述等式的m必定唯一存在。所以解密RSA 的流程 m = c d mod n，可以分解为

m1 = c^d mod p
m2 = c^d mod q

然后再计算m

但是等式 c d mod p 或者 c d mod q ，模数虽然从n降为p或q了，但是私钥指数指数d还是较大，运算还是比较消耗性能。所以我们还需要降低指数。
降d

仔细看等式 c d mod p

令d = k(p-1) + r 则 c^d mod p
= c^k(p-1)+r mod p
= c^r * c^k(p-1) mod p
因为 c^(p-1) mod p = 1 （欧拉定理）
= c^r mod p

r 是 d 除 p-1 的余数，即 r = d mod (p-1) 所以 c^d mod p 可以降阶为 c^(d mod p-1)mod p，同理，c^d mod q可以降阶为 c^(d mod q-1) mod q。
可令

dp = d mod p-1
dq = d mod q-1

这样 m1 和 m2 就降为

m1 = c^dp mod p
m2 = c^dq mod q

解密
模数都降的差不多了。想要求解明文，除了上述的 p、q、d、dp、dq，我们还需要 q 对 p 的逆元

qinv = q^-1 mod p

结合上述的公式，我们得到最终的明文公式

h = qinv(m1−m2) mod p
m = m2+hq mod p∗q

dp泄露
这玩意看的好不理解，nkctf中有涉及，就先了解一下

from Crypto.Util.number import *
import gmpy2
for i in range(1,e):
    if (dp*e-1)%i == 0:
        if (n%((dp*e-1)//i+1)) == 0:
            p = (dp*e-1)//i+1
            q = n // p#注意都是整除
            phi_n = (p-1)*(q-1)
            d = gmpy2.invert(e,phi_n)
            m = pow(c,d,n)
print(long_to_bytes(m))

libnum库常用函数：http://t.csdn.cn/igqKk

[SWPUCTF 2021 新生赛]ez_rsa

下载附件，给了我们p，q，e，让我们求d

p = 1325465431
q = 152317153
e = 65537

常规脚本

[BJDCTF 2020]rsa

给了我们一个python文件

from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120  13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''

给了我们输出结果
复习代码得到相应数据

c1=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
pow(294,e,n)=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c2=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047

没有e，那就需要我们先求e
要用到gmpy2这个库，先了解一下

最后求m

鲲鹏杯测试-EzRSA

这题和上题差不多，同样是求最大公因数，就是需要求两个m

# print(len(flag))
m1 = bytes_to_long(flag[:35].encode())
m2 = bytes_to_long(flag[35:].encode())
p = getStrongPrime(1024)
q1 = getStrongPrime(1024)
q2 = getStrongPrime(1024)
n1 = p*q2
n2 = p*q1

e = 65537

c1 = pow(m1,e,n1)
c2 = pow(m2,e,n2)

print(n1,n2)
print(c1,c2)

# n1 = 18422887619025499093500253269982403514726734277290130931951684733409266757764552588136835586520444091497616122502433703822553005925827145870143883796284263591709668204024923666139247443142798131329126460191906142706434731369042637394062321362776602627815833196839001977393492553326032070349543153752206738330860921833423029246405453226702292877915919284243207730531441343099665326828244449330966931286027668460212888401368703925131438510132292325800955352080008624087828820341494478162275382644669874909677148502171755139738168028969162526912645296896922620947089851413946790871101005207462066220637348687873404340687
# n2 = 24627238962728348376943815027705870674921397560982001460282793626331598002575628339078099521337506974273153395720153505527191716182556511162045486888904879613572145129703667870896581000278381201200220298658273449218381116870437172472113285378423666989971859902485623881932028927127508183296068229924950579577585886324594991469272086469095401166676668290812950337926472248122812412724596895010295386332476713199623619123717948312334240984316891006096260515702314938536822982292177111570982341289847648748526252397867488845123136053713512073205140442674942808737453465421327055140020553239138011846499457463318570283521
# c1 = 6284446110115714055813522467658985189840095779526440780412230500922915951666616640923441039453164391416455207092370270421706629536475592428608955473690820297943288217585504761608108771783834384917615319108794406823684798622519757621754873542804639306271552082323646592520118896866755358538308654982293434096188853579365731748552860101384331709922630925898131971465741935642615424849284783129579175640029485331061512766064706551698777789337684638173847046736104282221158607030704351874945142922941782721605049545683790191848198970770948616191722711742800378016072064840738915101836555390433720255813340065960884063899
# c2 = 19701647365692546726952225736637497258695131141374046521294489080965974622270697254863583369643494778983749595264544389398444139943788137653845896238895688293658927167034461397570791042001989763664114832113375325985401879218827556199571607481622094508566261042253234191936907380260805350833037184767286096205214538324075862070786916740941195478731499000640584820531907741554108294239422528858821234407414082087337559936811047388906289334635248998101990682898604073934887242100362055589959540531254283572133377676380544975391568187608237539246773626102150837822529055031326871977430055047643381030535060217496161063206

脚本

import libnum
import gmpy2
n1 = 18422887619025499093500253269982403514726734277290130931951684733409266757764552588136835586520444091497616122502433703822553005925827145870143883796284263591709668204024923666139247443142798131329126460191906142706434731369042637394062321362776602627815833196839001977393492553326032070349543153752206738330860921833423029246405453226702292877915919284243207730531441343099665326828244449330966931286027668460212888401368703925131438510132292325800955352080008624087828820341494478162275382644669874909677148502171755139738168028969162526912645296896922620947089851413946790871101005207462066220637348687873404340687
n2 = 24627238962728348376943815027705870674921397560982001460282793626331598002575628339078099521337506974273153395720153505527191716182556511162045486888904879613572145129703667870896581000278381201200220298658273449218381116870437172472113285378423666989971859902485623881932028927127508183296068229924950579577585886324594991469272086469095401166676668290812950337926472248122812412724596895010295386332476713199623619123717948312334240984316891006096260515702314938536822982292177111570982341289847648748526252397867488845123136053713512073205140442674942808737453465421327055140020553239138011846499457463318570283521
c1 = 6284446110115714055813522467658985189840095779526440780412230500922915951666616640923441039453164391416455207092370270421706629536475592428608955473690820297943288217585504761608108771783834384917615319108794406823684798622519757621754873542804639306271552082323646592520118896866755358538308654982293434096188853579365731748552860101384331709922630925898131971465741935642615424849284783129579175640029485331061512766064706551698777789337684638173847046736104282221158607030704351874945142922941782721605049545683790191848198970770948616191722711742800378016072064840738915101836555390433720255813340065960884063899
c2 = 19701647365692546726952225736637497258695131141374046521294489080965974622270697254863583369643494778983749595264544389398444139943788137653845896238895688293658927167034461397570791042001989763664114832113375325985401879218827556199571607481622094508566261042253234191936907380260805350833037184767286096205214538324075862070786916740941195478731499000640584820531907741554108294239422528858821234407414082087337559936811047388906289334635248998101990682898604073934887242100362055589959540531254283572133377676380544975391568187608237539246773626102150837822529055031326871977430055047643381030535060217496161063206
p=gmpy2.gcd(n1,n2)
q1=n1//p
q2=n2//p
phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)
e = 65537
d1=libnum.invmod(e,phi1)
d2=libnum.invmod(e,phi2)
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
print(libnum.n2s(int(m1)))
print(libnum.n2s(int(m2)))

[2023nkctf]baby_RSA

from Crypto.Util.number import *
nbit = 512
flag='****************************'

p=getPrime(nbit)
q=getPrime(nbit)
e=65537
n=p*q
m= bytes_to_long(bytes(flag.encode()))
P = pow(m,p,n)
Q = pow(m,q,n)
N=P*Q
phi_N=(P-1)*(Q-1)
d=inverse(e,phi_N)
dP=d%(P-1)
print('n = ',n)
print('N = ',N)
print('dP = ',dP)


n =  114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N =  1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP =  33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263

从题目可以看出首先要利用dp泄露求出P,Q，然后将p，q当作e1，e2的共模，

脚本

from Crypto.Util.number import *
import libnum
n =  114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N =  1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP =  33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263
e=65537
for i in range(1,65537): #在范围（1，e）中进行遍历
    P=(dp*e-1)//i==0
    if N%(((dp*e-1)//i)+1)==0: #存在p，使得n能被p整除
        P=((dp*e-1//i)+1)
        Q=N//((dp*e-1//i)+1)
        # phi=(q-1)(p-1) #欧拉定理
        # d=gp.invert(e,phi) #求模逆
        # m=pow(c,d,n) #快速求幂取模运算
        print(P,Q)
        PR.<m>=PolynomialRing(Zmod(n))
        f=m^2-(P+Q)*m+P*Q
        x0=f.small_roots()
        print(libnum.n2s(int(x0[0])))
        break

[羊城杯2021]Bigrsa

共享素数是指RSA加密时进行了两次加密，并且给出了加密钥e，两次加密的n1和n2，密文c。
题目

from Crypto.Util.number import *
from flag import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
print(m)
c = pow(m, e, n1)  # c=(m^e)%n1
c = pow(c, e, n2)  # c=(c^e)%n2
print(c)
# 加密了两次明文



# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

题目中对明文进行了两次的加密，分别使用两次的n，要通过密文解出明文m，那么就得知道两次加密的解密钥d，要求出解密钥d就得需要知道p，q通过求逆元的方法求出d。但是n1和n2的值非常大，通过爆破求因式分解显示不太可能。因此可以看看两个n之间是否存在共用的素数。

import libnum
import gmpy2
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p=gmpy2.gcd(n1,n2)
q1=n1//p
q2=n2//p
phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)
d1=libnum.invmod(e,phi1)
d2=libnum.invmod(e,phi2)
c=pow(c,d2,n2)
m=pow(c,d1,n1)
print(libnum.n2s(int(m)))